package com.algo.sort;

import org.junit.Test;

import java.util.Arrays;

public class InsertionSort {
    public void insertionSort(int[] a, int n) {
        if(n<=1) return;
        for(int i=1;i<n;i++){
            int value=a[i];
            int j=i-1;
            for(;j>=0;--j){
                if(a[j]>a[i]){
                    a[j+1]=a[j];
                }else{
                    break;
                }
            }
            a[j+1]=value;
        }

    }

    @Test
    public void test(){
        int[] a={2,1,4,2,5,4,9,7,5};
        System.out.println(Arrays.toString(test(a,a.length)));
    }

    public int[] test(int[] a,int n){
        if(a.length<=1) return a;

        for(int i=1;i<a.length;++i){
            int value=a[i];

            for(int j=i-1;j>=0;j--){
                if(value<a[j]){
                    a[j+1]=a[j];
                }else{
                    a[j]=value;
                    break;
                }
            }
            //a[j+1]=value;

        }
        return a;
    }
}
